package DP;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname 打家劫舍III337
 * @Description TODO
 * @Date 2023/3/28 12:52
 * @Created by xjl
 */
public class 打家劫舍III337 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }

    public int rob2(TreeNode root) {
        //res 二维数组 res 0   res1
        //res 0      不抢劫当前节点的最大值
        //res 1      抢劫当前节点的最大值
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    /*
        返回一个res
    */
    public int[] dp(TreeNode root){
        if(root == null)    {return new int[]{0,0};}
        int[] left  = dp(root.left);
        int[] right = dp(root.right);
        int rob     = root.val + left[0] + right[0];
        int not_rob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]) ;
        return new int[]{not_rob, rob};
    }
}
